﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphLibrary.Algorithms
{
    sealed public class DepthFirstSearch<TVertex, TEdge> : GraphAlgorithm<TVertex, TEdge>
        where TEdge : IEdge<TVertex>
    {
        //GraphColor.White-не посещенные вершины,
        //GraphColor.Black-посещенные вершины
        Dictionary<TVertex, GraphColor> _colours = new Dictionary<TVertex, GraphColor>();
        //лес поиска в глубину
        Dictionary<TVertex, TVertex> _depthFirstForest = new Dictionary<TVertex, TVertex>();

        int time = 0;

        public DepthFirstSearch(IGraph<TVertex, TEdge> graph)
        {
            Graph = graph;
        }

        public Dictionary<TVertex, TVertex> DepthFirstForest
        {
            get
            {
                return _depthFirstForest;
            }
        }
        //момент обнаружения вершины
        Dictionary<TVertex, int> _enterTimestamps = new Dictionary<TVertex, int>();
        public Dictionary<TVertex, int> EnterTimestamps
        {
            get
            {
                return _enterTimestamps;
            }
        }
        //момент, когда была закончена обработка всех смешных вершин с данной
        Dictionary<TVertex, int> _exitTimestamps = new Dictionary<TVertex, int>();
        public Dictionary<TVertex, int> ExitTimestamps
        {
            get
            {
                return _exitTimestamps;
            }
        }        

        //событие, инициирующееся при обнаружении вершины
        public event VertexAction DiscoverVertex;

        void OnDiscoverVertex(TVertex v)
        {
            if (DiscoverVertex != null)
                DiscoverVertex(v);
        }

        //событие, инициирующееся в тот момент, когда все соседи вершины обнаружены
        public event VertexAction LeaveVertex;

        void OnLeaveVertex(TVertex v)
        {
            if (LeaveVertex != null)
                LeaveVertex(v);
        }

        //событие, инициирующееся когда найдена очередная компонента связности
        public event GraphAction ChangeConnectedComponent;

        void OnChangeConnectedComponent()
        {
            if (ChangeConnectedComponent != null)
                ChangeConnectedComponent();
        }

        public event GraphAction CycleHasBeenFound;

        void OnFindCycle()
        {
            if (CycleHasBeenFound != null)
                CycleHasBeenFound();
        }

        void Initialize()
        {
            foreach (TVertex v in Graph.Vertices)
            {
                _colours.Add(v, GraphColor.White);
            }
        }

        public void Execute()
        {
            Initialize();
            foreach (TVertex v in Graph.Vertices)
            {
                if (_colours[v] == GraphColor.White)
                {
                    OnChangeConnectedComponent();
                    Visit(v);
                }
            }
        }

        void Visit(TVertex vertex)
        {
            _colours[vertex] = GraphColor.Gray;
            OnDiscoverVertex(vertex);
            _enterTimestamps[vertex] = time++;
            foreach (TVertex v in Graph.AdjacentVertices(vertex))
            {
                if (_colours[v] == GraphColor.White)
                {
                    _depthFirstForest[v] = vertex;
                    Visit(v);
                }
                else
                if (_colours[v] == GraphColor.Gray)
                {
                    OnFindCycle();
                }
            }
            _colours[vertex] = GraphColor.Black;
            OnLeaveVertex(vertex);
            _exitTimestamps[vertex] = time++;
        }
    }
}
